1. Field of the Invention
The present invention relates to adaptive channel encoding methods and devices for communications systems, and in particular, to adaptive channel encoding methods and devices for use in transmission of voice and data.
2. Description of the Related Art
A turbo encoder, constituted in a parallel or serial structure, generates parity symbols from an input N-information bit frame with two simple component (or constituent) encoders. It uses a recursive systematic convolutional (RSC) code as a component (or constituent) code.
FIG. 1 is a block diagram of a conventional parallel turbo encoder, disclosed in U.S. Pat. No. 5,446,747 by Berrou. In the turbo encoder of FIG. 1, an interleaver 12 is interposed between first and second component encoders 11 and 13. The interleaver 12 has a size equivalent to the frame length N of the input information bits, and modifies the sequence of information bits received in the second component encoder 13 to reduce correlation between information bits. FIG. 2 is a block diagram of a conventional serial turbo encoder also having the interleaver 12 connected between the first and second component encoders 11 and 13.
The above turbo encoders produce a turbo code for use in space communications. Though a constraint length K in the component encoders 11 and 13 is shorter than that of a conventional convolutional code (i.e., K=9), the interleaver 12 uses a very large memory, resulting in a very long delay at decoding.
FIG. 3 is a block diagram of a turbo decoder for decoding the output of the parallel turbo encoder shown in FIG. 1, also disclosed in U.S. Pat. No. 5,446,747 by Berrou. FIG. 4 is a block diagram of a turbo decoder for decoding the output of the serial turbo encoder shown in FIG. 2, proposed by Benedetto in an article of IEEE Electronics Letters, Vol. 32, No. 13, June 1996.
The parallel turbo decoder of FIG. 3 advantageously enhances performance characteristics in terms of bit error rate (BER) by repeatedly decoding input data in frame units, using an iterative decoding algorithm. An interleaver 323 contributes to an increase in an error correction capability by distributing burst error patterns which were not corrected by a first decoder 319, prior to correction of the burst error patterns in a second decoder 327.
The iterative decoding refers to repeated decoding of symbols which were decoded in a specific procedure, using resulting extrinsic information, to achieve excellent decoding performance. Iterative decoding algorithms are SOVA (Soft-Output Viterbi Algorithm: see Proceedings of IEEE Vehicular Technology Conference, pp. 941-944, May 1993) and MAP (Maximum Aposteriori Probability: see IEEE Transactions on Information Theory, pp. 429-445, Vol. 42, No. 2, March 1996). SOVA is a modification of a Viterbi algorithm which produces a soft decision output and can minimize codeword error rate. On the other hand, MAP can minimize symbol error rate.
In the decoder of FIG. 3, outputs y.sub.1k and y.sub.2k of a depuncturer 313 are y.sub.k and zero, respectively, when a parity symbol y.sub.k is received from the first component encoder 11 of FIG. 1, whereas they are zero and y.sub.k, respectively, when the parity symbol y.sub.k is received from the second component encoder 13 of FIG. 1. Z.sub.k+1 is a soft decision symbol used as extrinsic information in an iterative decoding algorithm and an input for decoding in a next stage. Data elements (D) obtained by subjecting the Z.sub.k+1 of the final decoding stage to hard decision are taken into account at output of the last module as intended. The performance of the turbo code depends on interleaver size, interleaver structure, and the number of iterative decodings.
As shown in FIG. 1, the turbo encoder includes the interleaver 12. The interleaver 12 causes turbo encoding/decoding to be implemented in frame units. Thus, the complexity of turbo code is proportional to the product of frame size of a memory necessary for first and second iterative decoders 319 and 327 shown in FIG. 3 and the state number of component codes for the first and second component encoders 11 and 13. The turbo code cannot find its application in voice and data transmission due to use of very large frames. Increasing the state number of the component codes for the turbo encoder in order to achieve better performance leads to increased complexity of the first and second component encoders 11 and 13.
With a burst error in the decoder as shown in FIG. 3, the output of the first iterative decoder 319 has a correlation, which impedes reliable decoding in the second iterative decoder 327 in the next decoding stage. Hence, errors are incurred in a whole block and cannot be corrected in a next iterative decoding stage. In this context, there is an ever increasing need for an interleaver and a deinterleaver which can distribute burst errors in a single frame of a code subject to iterative decoding without correlation.
Due to the advantage of low correlation, a random interleaver increases the performance of the turbo code. With small frame size, however, the random interleaver has limitations in its effectiveness for distributing burst errors without correlation and requires a look-up table. Hence, voice transmission or low-rate data transmission require small frame size and a small number of component code states to minimize delay time. Voice transmission or low-rate data transmission further need a structured interleaver. In short, the conventional turbo code is not viable in the voice and data transmission because of the unacceptability of the constraint length of the component codes and the large interleaver. Nevertheless, efforts are increasingly expended on realization of an encoder and a decoder for a communications system, taking the advantages of the conventional turbo code into account.
Therefore, a need exists for a turbo encoder having a performance equal to or higher than that of a convolutional encoder in a conventional communications system. A further need exists for an interleaver having excellent performance with small component code states and minimized delay time. Though the performance of the interleaver 12 of FIG. 1 or 2 for use in a turbo encoder is generally proportional to the interleaver size, the frame size of the turbo code is limited. In this case, it is preferable to use an interleaver that maximizes a minimum hamming distance of the turbo code in terms of a block code. A structured interleaver can be employed for small frames.